#include <iostream>
#include <ctime>

#include "node.hpp"

//function signatures
//creates initial state
Node setup();
//picks and expands next node
bool expand(std::vector<Node*> &,Node **);
//prints results
void print(Node *);

int main(){
	Node root = setup();
	Node *solution = &root;
	std::vector<Node*> list;
	std::clock_t time;
	list.push_back(&root);
	time = std::clock();
	if(Node::size == 2 || Node::size == 3){
		std::cout << "no solution" << std::endl;
		time = std::clock() - time;
	}
	else{
		//1800 seconds = 30 minutes
		while(expand(list,&solution) && (((std::clock() - time)/CLOCKS_PER_SEC) <= 1800)){
			if(solution->conflicts <= 0){
				break;
			}
		}
		time = std::clock() - time;
		print(solution);
	}
	std::cout << ((double) time)/CLOCKS_PER_SEC << " seconds" << std::endl;
	//DEBUG STATEMENT
	//std::system("pause");
	return 0;
}

Node setup(){
	int size,maxMoves,x,y;
	std::vector< std::pair<int,int> > init;
	std::cin >> size;
	std::cin >> maxMoves;
	for(int i=0;i<size;i++){
		std::cin >> x; //row
		std::cin >> y; //col
		init.push_back(std::pair<int,int>(x,y));
	}
	return Node(init,size,maxMoves,0);
}

bool expand(std::vector<Node*> &list,Node **solution){
	if(list.size() <=0){
		return false;
	}
	Node *next;
	std::vector<Node*>::iterator inext;
	inext = list.begin();
	for(std::vector<Node*>::iterator i=list.begin()+1;i!=list.end();i++){
		if(((*i)->h + (*i)->moves) < ((*inext)->h + (*inext)->moves)){
			inext = i;
		}
		else if(((*i)->h + (*i)->moves) == ((*inext)->h + (*inext)->moves)){
			if((*i)->conflicts < (*inext)->conflicts){
				inext = i;
			}
		}
	}
	next = *inext;
	list.erase(inext);
	if((next->moves >= next->maxMoves) || (next->conflicts <= 0) || next->done){
		next->done = true;
	}
	else{
		next->expand(list);
		next->done = true;
	}
	if(next->conflicts < (*solution)->conflicts){
		(*solution) = next;
	}
	else if(next->conflicts == (*solution)->conflicts){
		if((next->moves + next->h) < ((*solution)->moves +(*solution)->h)){
			(*solution) = next;
		}
	}
	return true;
}

void print(Node *solution){
	std::cout << solution->conflicts << " conflicts" << std::endl;
	for(std::vector< std::pair<int,int> >::iterator i=solution->queens.begin();i!=solution->queens.end();i++){
		std::cout << i->first << " " << i->second << std::endl;
	}
}